package newcoder_exp.justPractise;
import java.util.*;
import org.junit.*;

import tree.TreeNode;
import tree.TreeUtils;
public class NC62 {
    public class Solution {
        //要求：
        
        /*
        1. 子树为平衡二叉树
        2. 左右子树的高度
        */
            
        public boolean IsBalanced_Solution(TreeNode root) {
              return dfs(root).isBBT; 
        }
        
        public Info dfs(TreeNode root) {
            if (root == null) return new Info(true, 0);
            Info left = dfs(root.left);
            if (!left.isBBT) return left;
            Info right = dfs(root.right);
            if (!right.isBBT) return right;
            if (Math.abs(left.height - right.height) > 1) {
                left.isBBT = false;
                return left;
            }
            left.height = Math.max(left.height, right.height) + 1;
            return left;
        }
        public class Info {
            boolean isBBT;
            int height;
            public Info(boolean isBBT, int height) {
                this.isBBT = isBBT;
                this.height = height;
            }
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        // String[] nums = new int[]{};
        String str = "{1,2,3,4,5,#,#,#,#,6}";
        TreeNode root = TreeUtils.deserialization(str);
        System.out.println(s.IsBalanced_Solution(root));
        System.out.println();
    }
}
